package 代码记录.剑指offer错题本;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zx
 * @create 2022-06-01 12:20
 */
public class 栈的压入弹出序列_31 {
    /**
     借用一个辅助栈stackstack,模拟压入/弹出操作的排列.根据是否模拟成功,即可得到结果.
     入栈操作：按照压栈序列的顺序执行.
     出栈操作：每次入栈后,循环判断"栈顶元素 == 弹出序列的当前元素"是否成立,将符合弹出序列顺序的栈顶元素全部弹出

     * @return 不懂可以看看官方的动态图解
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque();
        int i = 0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();//若stack为空,则此弹出序列合法
    }
}
